package com.leet.code.simple_array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: WYG
 * @time: 2020/12/26 8:55
 */

public class MinimumAbsDifference {
    //未超时
    //首先理解什么是最小绝对差:是差的绝对值还是绝对值的差?从通过的题解来看就是差的绝对值,比绝对值的差要简单!
    //最小绝对差肯定在排序之后相邻的两个元素之间的差之中
    public List<List<Integer>> new_minimumAbsDifference(int[] arr) {
        //首先对数组进行排序,方便求最小绝对差以及后续的升序输出结果
        Arrays.sort(arr);
        List<List<Integer>> res = new ArrayList<>();
        //首先将第一对值的差赋给最小值,然后再求最小绝对差
        int min = arr[1] - arr[0];
        //求最小绝对差并将其对应的结果写入结果list中
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i] - arr[i - 1];
            // 找到新的最小差,清空原有结果
            if (tmp < min) {
                min = tmp;
                res.clear();
            }
            // 如果是最小差,记录
            if (tmp == min) {
                List<Integer> item = new ArrayList<>(2);
                item.add(arr[i - 1]);
                item.add(arr[i]);
                res.add(item);
            }
        }
        return res;
    }

    //超时
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int min = Math.abs(arr[1] - arr[0]);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (Math.abs(arr[j] - arr[i]) < min) {
                    min = Math.abs(arr[j] - arr[i]);
                }
            }
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (Math.abs(arr[j] - arr[i]) == min) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(arr[i]);
                    temp.add(arr[j]);
                    res.add(temp);
                }
            }
        }
        return res;
    }
}
